package com.example.system.class11;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2022/7/30
 * @Author Jonathan
 * @Description X祖先节点 求交集
 */
public class Code02_XAncestor {
    private static int index = 0;

    private static Node x = null;

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 8, 12, null, null, null, 4, 3, null, null, 9, null, null};
        Node root = createBST(arr);
        final List<Node> xAncestor = findXAncestor(x, root);
        for (Node node : xAncestor) {
            System.out.println("node:" + node);
        }

    }


    /**
     * 寻找x节点的祖先节点
     *
     * @param x    x节点
     * @param root 根节点
     */
    public static List<Node> findXAncestor(Node x, Node root) {
        List<Node> list1 = new ArrayList<>();
        List<Node> list2 = new ArrayList<>();
        List<Node> ans = new ArrayList<>();
        preOrder(root, list1);
        postOrder(root, list2);
        final List<Node> list11 = list1.subList(0, list1.indexOf(x)); // 先序遍历的前半部分
        final List<Node> list22 = list2.subList(list2.indexOf(x), list2.size()); // 后续遍历的后半部分
        for (Node node : list11) {
            if (list22.contains(node)) {
                ans.add(node);
            }
        }
        return ans;
    }


    // 先序
    private static void preOrder(Node root, List<Node> ans) {
        if (root == null) {
            return;
        }
        ans.add(root);
        preOrder(root.left, ans);
        preOrder(root.right, ans);
    }


    private static void postOrder(Node root, List<Node> ans) {
        if (root == null) {
            return;
        }
        postOrder(root.left, ans);
        postOrder(root.right, ans);
        ans.add(root);
    }


    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node[" +
                    "value=" + value +
                    ']';
        }
    }

    public static Node createBST(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create(arr);
    }

    // 借助全局变量实现
    public static Node create(Integer[] arr) {
        Integer value = arr[index++];
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        // 给x节点赋值
        if (value == 3) {
            x = node;
        }
        node.left = create(arr);
        node.right = create(arr);
        return node;
    }

}
